#include "delaunay.h"

bool compararAngulos(const pair<int,double>& a, const pair<int,double>& b)
{
    return(a.second < b.second);
}

bool compararIDangulo(const ponto_angulo& a, const ponto_angulo& b)
{
    return(a.angulo < b.angulo);
}

double anguloOrientado(const Vector &v)
{
    double angulo = anguloGrau(Vector("1.0,0.0,0.0"),v);
    // Verificar o sinal da coordenada "y" do vetor "v":
    if (v(1) < 0.0) return(360-angulo);
    return(angulo);
}

Delaunay::Delaunay(Grupo g): grupo_nome(g.get_nome()), vertices(g.get_pontos())
{
    // Reservar espaÃ§o na lista de arestas:
    arestas_respostas.reserve(vertices.size());
    // Alocar a lista de arestas (usaremos cada posicao da lista como o ID do ponto):
    for (int i=0 ; i<vertices.size() ; i++) arestas_respostas.append(QSet<int>());
}

void Delaunay::imprimirVertices(const QList<int> &L)
{
    cout<<"tamanho = "<<L.size()<<endl;
    foreach(const int& item,L)
    {
        cout<<"ID = "<<item<<" : ";
        vertices[item].imprimir();
        cout<<endl;
    }
}

const QList<Point>& Delaunay::getVertices()
{
    return(vertices);
}

const QList<QSet<int> >& Delaunay::getArestas()
{
    return(arestas_respostas);
}

const QList<triangulo>& Delaunay::getTriangulos()
{
    return(triangulos);
}

void Delaunay::addAresta(QList< QSet<int> >& lista_arestas, int a,int b)
{
    // Protecao contra a criacao de arestas do tipo "laco":
    if (a != b)
    {
        lista_arestas[a].insert(b);
        lista_arestas[b].insert(a);
    }
}

void Delaunay::delAresta(QList< QSet<int> >& lista_arestas, int a,int b)
{
    lista_arestas[a].remove(b);
    lista_arestas[b].remove(a);
}

bool Delaunay::existeAresta(const QList< QSet<int> >& lista_arestas, int a,int b) const
{
    // Pega a lista de adjacencias do vÃ©rtice "a" e procura o vÃ©rtice "b":
    foreach(const int& adj,lista_arestas[a].toList()) if (adj == b) return(true);
    return(false);
}

QList<int> Delaunay::arestasAntiHorario(int ponto_id)
{
    // A lista abaixo vai conter o id do ponto e o seu Ã¢ngulo:
    QList< pair<int,double> > lista_angulos;

    foreach(const int& adj,arestas_respostas[ponto_id].toList())
    {
        // Calcular o vetor "v" que vai do ponto "ponto_id" ao ponto "adj":
        Vector v(vertices[adj] - vertices[ponto_id]);
        // Colocar na lista o id do ponto "adj", juntamente com o valor de seu Ã¢ngulo orientado:
        lista_angulos.append(pair<int,double>(adj,anguloOrientado(v)));
    }

    // Ordenar a lista (pelos Ã¢ngulos):
    qSort(lista_angulos.begin(),lista_angulos.end(),compararAngulos);

    // Selecionar sÃ³ os IDs das arestas da lista de IDs e Ã¢ngulos:
    QList<int> lista_ids;
    for(int i=0 ; i<lista_angulos.size() ; i++) lista_ids.append(lista_angulos[i].first);

    // Retornar a lista com os IDs das arestas:
    return(lista_ids);
}

QList<int> Delaunay::arestasHorario(int ponto_id)
{
    return(arestasAntiHorario(ponto_id));
    /*
    // Pegar a lista de arestas no sentido anti-horario:
    QList<int> lista_ids = arestasAntiHorario(ponto_id);

    // Inverter a lista de IDs (inverter o sentido):
    for (int i=0 ; i < (lista_ids.size()/2) ; i++)
        lista_ids.swap(i,lista_ids.size()-(1+i));

    // Retornar a lista com os IDs das arestas:
    return(lista_ids);
    */
}

void Delaunay::imprimirArestas()
{
    for (int i=0 ; i<arestas_respostas.size() ; i++)
    {
        cout<<i<<": ";
        foreach(const int& adj,arestas_respostas[i].toList()) cout<<adj<<", ";
        cout<<endl;
    }
}

QList<int> Delaunay::calcularAnguloMax(aresta a)
{
    QList<ponto_angulo> lista_ids_angulo;
    QList<ponto_angulo> lista_ids_angulo_valido;
    QList<int> resp;

    for (int i=0 ; i<vertices.size() ; i++)
        if ((i != a.ini) && (i != a.fim))
            lista_ids_angulo.append(ponto_angulo(i,anguloGrau(vertices[a.ini]-vertices[i],vertices[a.fim]-vertices[i])));

    // Checar s eo triangulo formado por um ponto da lista e a aresta "a" já existe:
    for (int i=0 ; i<lista_ids_angulo.size() ; i++)
        if (!existeTriangulo(lista_ids_angulo.at(i).ponto,a))
            lista_ids_angulo_valido.append(lista_ids_angulo[i]);

    lista_ids_angulo.clear();

    // Ordenar crescentemente a lista (pelos angulos):
    qSort(lista_ids_angulo_valido.begin(),lista_ids_angulo_valido.end(),compararIDangulo);

    // Pegar o valor do maior angulo:
    double maior = lista_ids_angulo_valido.back().angulo;

    // Selecionar os maior(es) angulo(s):
    for (int i=0 ; i<lista_ids_angulo_valido.size() ; i++)
        if (lista_ids_angulo_valido[i].angulo == maior)
            resp.append(lista_ids_angulo_valido[i].ponto);

    return(resp);
}

void Delaunay::formarTriangulo(int p, aresta a)
{
    triangulo triangulo_temp(p,a.ini,a.fim);

    /// *** DEBUG ********************************** ///
    cout<<"triangulo_temp:"<<endl;
    cout<<"triangulo_temp.a = "<<triangulo_temp.a<<endl;
    cout<<"triangulo_temp.b = "<<triangulo_temp.b<<endl;
    cout<<"triangulo_temp.c = "<<triangulo_temp.c<<endl;
    /// ******************************************** ///

    for (int i=0 ; i<triangulos.size() ; i++)
        if (comparaTriangulo(triangulos.at(i),triangulo_temp))
        {
            cout<<"AVISO: Um triangulo existente tentou entrar. DANGER!!!"<<endl;
            break;
        }

    triangulos.append(triangulo_temp);
}

void Delaunay::triangularizar()
{
    /// ====================== ///
    /// Comeco da triangulacao ///
    /// ====================== ///

    // Instanciar o metodo de Jarvis:
    Jarvis j(Grupo(grupo_nome,vertices));

    // Calcular o fecho convexo e pegar a lista com os IDs dos pontos dele:
    QList<int> pontos_fecho = Fecho(j.convexhull()).get_ids();

    if (pontos_fecho.size() == 0)
    {
        cout<<"AVISO: o fecho convexo esta vazio!"<<endl;
        return;
    }

    /// Lista com as arestas a visitar ///
    QList<aresta> arestas_a_visitar;
    /// FIM: Lista com as arestas a visitar ///

    /// Lista com as arestas do fecho convexo ///
    QList< QSet<int> > arestas_fecho;

    // Reservar espaco na lista de arestas do fecho:
    arestas_fecho.reserve(vertices.size());

    // Alocar a lista de arestas do fecho:
    for (int i=0 ; i<vertices.size() ; i++) arestas_fecho.append(QSet<int>());

    // Pegar o o ID do primeiro ponto do fecho e coloca-lo no final
    // da lista de pontos do fecho para facilitar a coleta de arestas:
    pontos_fecho.push_back(pontos_fecho[0]);
    /// FIM Lista com as arestas do fecho convexo ///

    // A cada dois elementos consecutivos da lista "pontos_fecho",
    // eu tenho a aresta do fecho ([i-1],[i]) que eles formam.
    // Pegar cada uma dessas arestas e colocar-las nas duas listas
    // de arestas seguintes: "arestas_fecho" e "arestas_respostas".
    for (int i=1 ; i<pontos_fecho.size() ; i++)
    {
        addAresta(arestas_fecho,pontos_fecho[i-1],pontos_fecho[i]);
        addAresta(arestas_respostas,pontos_fecho[i-1],pontos_fecho[i]);
        arestas_a_visitar.append(aresta(pontos_fecho[i-1],pontos_fecho[i]));
    }

    // Calcular numero maximo de triangulos (2 * n - v - 2):
    int numero_maximo_triangulos = 2 * vertices.size() - (pontos_fecho.size()-1) - 2;

    // Esvaziar a lista "pontos_fecho" que nao sera mais usada:
    pontos_fecho.clear();

    int numero_triangulos = 0;
    //while (numero_triangulos < numero_maximo_triangulos+2)
    while (arestas_a_visitar.size() > 0)
    {
        // Pegar a primeira aresta da lista de arestas visitadas:
        cout<<"arestas_a_visitar.at(0).size = "<<arestas_a_visitar.size()<<endl;
        //if (arestas_a_visitar.isEmpty()) break;//MUDAMOS ISSO!!

        aresta aresta_temp = arestas_a_visitar.at(0);

        // Gerar uma lista com os IDs do(s) ponto(s) que formam o maior Ã¢ngulo com a aresta "aresta_temp":
        QList<int> cadidatos_angulo_maximo = calcularAnguloMax(aresta_temp);

        while (cadidatos_angulo_maximo.size())
        {
            cout<<"*** loop.entrou: cadidatos_angulo_maximo.size() ***"<<endl;

            cout<<"cadidatos_angulo_maximo.size = "<<cadidatos_angulo_maximo.size()<<endl;

            // Remove e retorna o primeiro ponto da lista de cadidatos:
            int ponto_temp = cadidatos_angulo_maximo.takeFirst();

            aresta arestaA(ponto_temp,aresta_temp.ini);
            aresta arestaB(ponto_temp,aresta_temp.fim);

            if (existeAresta(arestas_respostas,ponto_temp,aresta_temp.ini)
                &&
                existeAresta(arestas_respostas,ponto_temp,aresta_temp.fim)
                    )
                continue;
            if (!arestaValida(arestaA) || !arestaValida(arestaB)) continue;
            else
            {
                // Adicionar as duas arestas do triangulo recem-formado na lista de resposta:
                addAresta(arestas_respostas,ponto_temp,aresta_temp.ini);
                addAresta(arestas_respostas,ponto_temp,aresta_temp.fim);

                // Caso estas duas novas arestas NÃO façam parte do fecho,
                // elas devem ser colocadas na lista "arestas_a_visitar":
                //if (!existeAresta(arestas_fecho,ponto_temp,aresta_temp.ini))
                    arestas_a_visitar.append(aresta(ponto_temp,aresta_temp.ini));
                //if (!existeAresta(arestas_fecho,ponto_temp,aresta_temp.fim))
                    arestas_a_visitar.append(aresta(ponto_temp,aresta_temp.fim));

                // Incrementar o numero de triangulos atual:
                numero_triangulos++;
                formarTriangulo(ponto_temp,aresta_temp);

                break;
            }
        }
        cout<<"*** loop.saiu: cadidatos_angulo_maximo.size() ***"<<endl;
        cout<<"arestas_a_visitar.removeFirst.size = "<<arestas_a_visitar.size()<<endl;
        arestas_a_visitar.removeFirst();
    }

    cout<<"\n*** GERADOS: "<<numero_triangulos<<" de "<<numero_maximo_triangulos<<" triangulos ***"<<endl;
    cout<<"*** LISTA DE TRIANGULOS ("<<triangulos.size()<<" triangulos) ***"<<endl;
    foreach(const triangulo& t,triangulos) cout<<"+ tri.ids: "<<t.a<<","<<t.b<<","<<t.c<<endl;
}

bool Delaunay::arestaCruzada(aresta a, aresta b)
{
    Vector vetAB = vertices[a.fim] - vertices[a.ini];
    Vector vetAC = vertices[b.ini] - vertices[a.ini];
    Vector vetAD = vertices[b.fim] - vertices[a.ini];
    Vector vetCD = vertices[b.fim] - vertices[b.ini];
    Vector vetCA = vertices[a.ini] - vertices[b.ini];
    Vector vetCB = vertices[a.fim] - vertices[b.ini];
    double p1 = dotProduct((vetAB*vetAC),(vetAB*vetAD));
    double p2 = dotProduct((vetCD*vetCA),(vetCD*vetCB));
    return (p1 < 0 && p2 < 0);
}

bool Delaunay::arestaValida(aresta a)
{
    for (int i=0 ; i<arestas_respostas.size() ; i++) {
        foreach(const int& adj,arestas_respostas[i].toList())
        {
            aresta arestaI(i,adj);
            if (arestaCruzada(a,arestaI))
                return false;
        }
    }
    return true;
}

bool Delaunay::existeTriangulo(int p, aresta a)
{
    triangulo t(a.ini,a.fim,p);
    for (int i=0 ; i<triangulos.size() ; i++)
        if (comparaTriangulo(triangulos.at(i),t))
            return true;
    return false;
}

bool Delaunay::comparaTriangulo(const triangulo& t1, const triangulo& t2)
{
    if ((t1.a == t2.a)
        &&
        (t1.b == t2.b)
        &&
        (t1.c == t2.c))
        return(true);
    return(false);
}
